import math
class Bnote:
    def __init__(self, date):
        self.left_child = None
        self.right_child = None
        self.date = date
        """
class Binary_tree:
    def __init__(self, header=None):
            self.header = header
"""
    def show_leaf(self, point):
        if point == None:
            return 0
        else:
            if point.left_child == None and point.right_child == None:
                print(point.date)
            else:
                self.show_leaf(point.left_child)
                self.show_leaf(point.right_child)

      def note_counter(self, point):
        if point == None:
            return 0
        else:
            m = self.note_counter(point.left_child)
            n = self.note_counter(point.right_child)
            return 1 + m + n
    def traverse1(self, note):
        if note == None:
            return
        else:
            print(note.date, end=" ")
            self.traverse1(note.left_child)
            self.traverse1(note.right_child)



if __name__ == '__main__':
    b = Bnote("A")
    p1 = Bnote("B")
    p2 = Bnote("C")
    p3 = Bnote("D")
    p4 = Bnote("E")
    p5 = Bnote("F")
    p6 = Bnote("G")
    b.left_child = p1
    b.right_child = p2
    p1.left_child = p3
    p3.right_child = p6
    p2.left_child = p4
    b.show_leaf(b)
"""
    tree = Binary_tree(b)
    tree.show_leaf(b)
"""
class BTNode:  # 二叉链中结点类
    def __init__(self, d=None):  # 构造方法
        self.data = d  # 结点值
        self.lchild = None  # 左孩子指针
        self.rchild = None  # 右孩子指针


class BTree:  # 二叉树类
    def __init__(self, d=None):  # 构造方法
        self.b = d  # 根结点指针

def PreOrder (t):  # 被PreOrder方法调用
    if t != None:
        print(t.data, end=' ')  # 访问根结点
        PreOrder (t.lchild)  # 先序遍历左子树
        PreOrder (t.rchild)  # 先序遍历右子树

def InOrder (t):  # 被InOrder方法调用
    if t != None:
        InOrder (t.lchild)  # 中序遍历左子树
        print(t.data, end=' ')  # 访问根结点
        InOrder (t.rchild)  # 中序遍历右子树


def PostOrder (t):  # 被PostOrder方法调用
    if t != None:
        PostOrder (t.lchild)  # 后序遍历左子树
        PostOrder (t.rchild)  # 后序遍历右子树
        print(t.data, end=' ')  # 访问根结点
def Displeaf (t):
    if t!=None:
        if t.lchild==None and t.rchild==None:
            print(t.data,end=' ')			    #输出叶子结点
        Displeaf (t.lchild)					#遍历左子树
        Displeaf (t.rchild)					#遍历右子树

def NodeCount (t):
    if t==None:									#空树结点个数为0
        return 0
    k=1 											#根结点计数 ，相当于访问根结点
    m=NodeCount (t.lchild)						#遍历求左子树的结点个数
    n=NodeCount (t.rchild)						#遍历求右子树的结点个数
    return k+m+n

def Level(t,x,h):
    if t==None:
        return 0								#空树不能找到该结点
    elif t.data==x:
        return h								#根结点即为所找,返回其层次
    else:
        l=Level(t.lchild,x,h+1 )			    #在左子树中查找
        if l!=0:
            return l						#左子树中找到了,返回其层次
        else:
            return Level(t.rchild,x,h+1 )	    #左子树中未找到,再在右子树中查找

if __name__ == '__main__':
    b = BTNode('A')  # 建立各个结点
    p  = BTNode('B')
    p2 = BTNode('C')
    p3 = BTNode('D')
    p4 = BTNode('E')
    p5 = BTNode('F')
    p6 = BTNode('G')
    b.lchild = p   # 建立结点之间的关系
    b.rchild = p2
    p .lchild = p3
    p3.rchild = p6
    p2.lchild = p4
    p2.rchild = p5
    bt = BTree(b)

    print("bt:", end=' ');
    print("先序序列:", end=' ');
    PreOrder (b);
    print()
    print("中序序列:", end=' ');
    InOrder (b);
    print()
    print("后序序列:", end=' ');
    PostOrder (b);
    print()
    print("层次序列:", end=' ');
    print()
    print("算法1 bt中结点个数:%d" % (NodeCount(b)))
    print("算法1 所有叶子结点", end=' ');
    Displeaf(b);
    print()
    x = 'C'
    print(x + "的层次=%d" % (Level(b, x,1)))
    x = 'F'
    print(x + "的层次=%d" % (Level(b, x,1)))
    x = 'X'
    print(x + "的层次=%d" % (Level(b, x,1)))






